#include<iostream>
template <typename Object>
//存储数据类型为Ob
class List
{
  private:
    struct Node
    //Node 类
    {
      Object data;//链表内的有效数据
      Node *prev;//指向前一个数据
      Node *next;//指向后一个数据

      Node( const Object & d = Object{ },Node *p = nullptr,Node *n = nullptr )
        :data{ d },prev{ p },next{ n }{ }
      //创建并赋值一个新节点
      Node( Object && d,Node *p = nullptr,Node *n = nullptr )
        :data{ std::move( d ) },prev{ p },next{ n }{ }
      //创建并赋值一个新节点
    };
  //定义一个双向链表的节点
  public:
    //const的迭代器
    class const_iterator
    {
      public:
        const_iterator( ) : current{ nullptr }
          { }
        //获得Object对象
	const Object & operator* ( ) const
	  { return retrieve( ); }
        //自增，前缀自增
	const_iterator & operator++ ( )
	{
	     current = current->next;
	     return *this;
	}
        //自增，后缀自增

	const_iterator operator++ ( int )
	{
	    const_iterator old = *this;
	    //原来的数据
	    ++( *this );
	    //调用前缀版本的自增
	    return old;
	    //返回原来的数据
	}
        //==重载
	bool operator== ( const const_iterator & rhs ) const
	  { return current == rhs.current; }
        //!=重载
	bool operator!= ( const const_iterator & rhs ) const
	  { return !( *this == rhs ); }

      protected:
	Node *current;
        //迭代器所指向的终点
	Object & retrieve( ) const
	  { return current->data; }

        const_iterator( Node *p ) : current{ p }
	  { }

	friend class List<Object>;
    };
    //迭代器
    class iterator : public const_iterator
    {
      public:
        iterator( )
	  { }
        //*重载
	Object & operator* ( )
	  { return const_iterator::retrieve( ); }
	const Object & operator* ( ) const
	  { return const_iterator::operator*( ); }

	iterator & operator++ ( )
	{
	    this->current = this->current->next;
	    return *this;
	}

	iterator operator++ ( int )
	{
	    iterator old = *this;
	    ++( *this );
	    return old;
	}
	
      protected:
        iterator( Node *p ) : const_iterator{ p }
	  { }

        friend class List<Object>;
    };
  public:
    //默认构造函数
    List( )
      { init( ); }
    //初始化
    //析构函数
    ~List( )
    {
        clear( );
	//清空链表
	//释放两个指针的内存
	delete head;
	delete tail;
    }

    List( const List & rhs )
    {
        init( );
	for( auto & x : rhs )
	    push_back( x );
    }

    List & operator= ( const List & rhs )
    {
        List copy = rhs;
	std::swap( *this, copy );
	return *this;
    }


    List( List && rhs )
      : theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
    {
      //初始化
        rhs.theSize = 0;
	rhs.head = nullptr;
	rhs.tail = nullptr;
    }

    List & operator= ( List && rhs )
    {
        std::swap( theSize, rhs.theSize );
	std::swap( head, rhs.head );
	std::swap( tail, rhs.tail );

	return *this;
    }
    //获取第一个迭代器
    iterator begin( )
      { return { head->next }; }
    //获取第一个数据的迭代器
    const_iterator begin( ) const
      { return { head->next }; }
    //获取最后一个迭代器
    iterator end( )
      { return { tail }; }
    //获取最后一个数据的迭代器
    const_iterator end( ) const
      { return { tail }; }
    //获得链表的大小
    int size( ) const
      { return theSize; }
    //是否为空链表
    bool empty( ) const
      { return size( ) == 0; }

    //清空整个链表
    void clear( )
    {
        while( !empty( ) )
	    pop_front( );
	    //从表头开始一个一个删除
    }
    //第一个数据的迭代器
    Object & front( )
      { return *begin( ); }
    const Object & front( ) const
      { return *begin( ); }
    //最后一个数据的迭代器
    Object & back( )
      { return *--end( ); }
    const Object & back( ) const
      { return *--end( ); }
    //在表头插入数据
    void push_front( const Object & x )
      { insert( begin( ), x ); }
    void push_front( Object && x )
      { insert( begin( ), std::move( x ) ); }
    //在表尾插入数据
    void push_back( const Object & x )
      { insert( end( ), x ); }
    void push_back( Object && x )
      { insert( end( ), std::move( x ) ); }
    //弹出最开始的数据
    void pop_front( )
      { erase( begin( ) ); }
    //弹出最后的数据
    void pop_back( )
      { erase( --end( ) ); }

    //在迭代器的位置插入数据
    iterator insert( iterator itr, const Object & x )
    {
	Node *p = itr.current;
	theSize++;
	return { p->prev = p->prev->next = new Node{ x, p->prev, p } };
	//构建新的指针
    } 
    iterator insert( iterator itr, Object && x )
    {
        Node *p = itr.current;
	theSize++;
	return { p->prev = p->prev->next
	                         = new Node{ std::move( x ), p->prev, p } };
    }

    //erase函数，删除迭代器指向的节点
    iterator erase( iterator itr )
    {
	 Node *p = itr.current;
	 iterator retVal{ p->next };
	 p->prev->next = p->next;
	 p->next->prev = p->prev;
	 delete p;
	 theSize--;

	 return retVal;
	 //返回下一个指针
    }

    //删除区间内的节点
    iterator erase( iterator from, iterator to )
    {
        for( iterator itr = from; itr != to; )
	    itr = erase( itr );

	return to;
    }

  private:
    int theSize;
    Node *head;
    Node *tail;
    
    void init( )
    //初始化
    {
        theSize = 0;
	head = new Node;
	tail = new Node;
	head->next = tail;
	tail->prev = head;
    }
};
